#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include "TreeNode.h"
using namespace std;

vector<vector<int>> zigzagLevelOrder(TreeNode *root)
{
    vector<vector<int>> res;
    if (!root)
        return res;
    vector<int> layer;
    queue<TreeNode *> Q;
    Q.push(root);
    int tmp = 1;
    while (!Q.empty())
    {
        int n = Q.size();
        for (int i = 0; i < n; i++)
        {
            TreeNode *cur = Q.front();
            layer.push_back(cur->val);
            Q.pop();
            if (tmp % 2 == 0)
            {
                if (cur->left)
                    Q.push(cur->left);
                if (cur->right)
                    Q.push(cur->right);
            }
            else
            {
                if (cur->right)
                    Q.push(cur->right);
                if (cur->left)
                    Q.push(cur->left);
            }
        }
        tmp++;
        res.push_back(layer);
        layer.clear();
    }
    return res;
}

int main()
{
    TreeNode *T1 = new TreeNode(1);
    TreeNode *T2 = new TreeNode(2);
    TreeNode *T7 = new TreeNode(7);
    TreeNode *T8 = new TreeNode(8);
    TreeNode *T4 = new TreeNode(4, T1, T2);
    TreeNode *T6 = new TreeNode(6, T7, T8);
    TreeNode *T5 = new TreeNode(5, T4, T6);
    vector<vector<int>> res = zigzagLevelOrder(T5);
    for (int i = 0; i < res.size(); i++)
    {
        printf("layer1: ");
        for (int j = 0; j < res[i].size(); j++)
        {
            printf("%d ", res[i][j]);
        }
    }
}
